package task1;


public class work6_2 {
    public static void main(String[] args) {

        int[] nums={3,2,1,5,6,4};

        int k=2;

        long start=System.currentTimeMillis();
        int result= findKthLargest(nums, k);
        System.out.println("耗时:"+(System.currentTimeMillis()-start)+"ms");
        System.out.println(result);
    }

    public static int findKthLargest(int[] nums, int k) {//快排计算第K大的数字
        int left=0;
        int right=nums.length-1;
        int p=-1;
        if(k<=0||k>nums.length) return Integer.MIN_VALUE;

        while (k!=p+1)
        {
            if(k-1<p)//k所对应的元素大于分治点元素
            {
                right=p-1;
            }else if(k-1>p)//k所对应的元素小于分治点元素
            {
                left=p+1;
            }
            p=partition(nums,left,right);//分治点
        }
        return nums[p];
    }

    public static int partition(int[] array, int left, int right) {

        int pivot=array[right];//临界值
        int sortIndex=left;//分治点

        for(int arrayIndex=sortIndex;arrayIndex<right;arrayIndex++)
        {
            if(array[arrayIndex]>pivot)//如果数组中的元素小于临界值
            {
                swap(array,arrayIndex,sortIndex);//则其与分治点的元素相交换且分治点右移一位
                sortIndex++;
            }
        }
        swap(array,sortIndex,right);//临界值归位，分治点元素与临界值交换
        return sortIndex;
    }

    public static void swap(int[] array, int left, int right) {//交换数组元素
        if(left==right)return;
        int temp=array[left];
        array[left]=array[right];
        array[right]=temp;
    }

}
